package twobranchTree.serialize;

import java.util.LinkedList;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/07
 * @author 王光浩
 * @Thinking 将给的树构造成完美二叉树，按照层序遍历的方式将该树的信息保留在字符串中（序列化），然后在反
 *           序列化时，同样按照层序的方式构造这颗树。
 * @Result 结果超出内存限制（原因是自己的数据量太大）
 */
public class MyMethodOne {
    // 将树按照层序方式进行序列化
    public String serialize(TreeNode root) {
        StringBuilder res=new StringBuilder();                  //保存序列化之后的结果
        LinkedList<TreeNode> queue=new LinkedList<TreeNode>();  //作为层序遍历的容器
        boolean judge=true;                                     //判断该层是否有非null节点
        if(root==null)return null;
        queue.add(root);                                  //序列化之后的开始标志
        while(!queue.isEmpty()) {
        	int size=queue.size(); //该层节点个数
        	TreeNode tem;
        	judge=false;
        	for(int i=0;i<size;i++) {
        		tem=queue.poll();
        		if(tem==null) {  //将不是满二叉树进行补全
        			res.append("null,");
        			queue.add(null); //将左右子树加入到队列中
        			queue.add(null);
        		}
        		else {
        			res.append(tem.val+",");
        			queue.add(tem.left);
        			queue.add(tem.right);
        			judge=true;
        		}
        	}
        	if(!judge) //刚刚遍历一层的数据中没有非null节点
        		break;
        }
        return res.toString();
    }

    // 将树按照反序列化的方式构造出一颗树
    public TreeNode deserialize(String data) {
    	if(data.length()==0)return null;
    	LinkedList<TreeNode> queue=new LinkedList<TreeNode>();  //保存当前层的上一层节点
    	boolean judge=true;                                     //判断该层是否存在非null节点
    	int first=1;  //记录下一个该访问的值的起始下标
    	int second=first+1; //记录下一个该访问值的结束下标
    	while(data.charAt(second)!=',')	{	
    		second++;
    	}
    	first=++second;
        TreeNode root=new TreeNode(Integer.valueOf(data.substring(first, second)));
        queue.add(root);
        //利用queue中上一层的节点连接到当前层的节点，进行反序列化
        while(!queue.isEmpty()) {
        	int size=queue.size(); //同样按照层序遍历的方式进行反序列化
        	judge=false;
        	for(int i=0;i<size;i++) {
        		TreeNode tem=queue.poll();
        		if(tem==null) {    //当节点为null
        			queue.add(null);
        			queue.add(null);
        			while(data.charAt(second)!=',') //当父节点为null时，在其中的子节点值一定为null，
        				second++;
        	    	first=++second;
        			while(data.charAt(second)!=',')
        				second++;
        	    	first=++second;
        		}
        		else {             //当节点非null
        			//连接左子树
        			while(data.charAt(second)!=',')
        				second++;
        			if(data.substring(first,second).equals("null")) {
        				queue.add(null);
        			}
        			else {
        				TreeNode left=new TreeNode(Integer.valueOf(data.substring(first,second)));
        				tem.left=left;
        				queue.add(left);
        				judge=true;
        			}
        			first=++second;
        			//连接右子树
        			while(data.charAt(second)!=',')
        				second++;
        			if(data.substring(first,second).equals("null")) {
        				queue.add(null);
        			}
        			else {
        				TreeNode right=new TreeNode(Integer.valueOf(data.substring(first,second)));
        				tem.right=right;
        				queue.add(right);
        				judge=true;
        			}
        			first=++second;
        		}
        	}
        	if(!judge)   //当刚刚遍历的一层节点中没有非null节点
        		break;
        }
        return root;
    }
}
